<!DOCTYPE html>
<html class="client-nojs vector-feature-night-mode-disabled vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-sticky-header-enabled" lang="en" dir="ltr"><head>
<meta charset="UTF-8">
<title>Distributed algorithm</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="canonical" href="https://en.wikipedia.org/wiki/Distributed_algorithm"> <link href="./mw/ext.cite.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/ext.math.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/user.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link rel="stylesheet" type="text/css" href="./mw/site.styles.css">
<link rel="stylesheet" type="text/css" href="./mw/noscript.css">
<link rel="stylesheet" type="text/css" href="./footer.css">
<link rel="stylesheet" type="text/css" href="./vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Distributed_algorithm rootpage-Distributed_algorithm skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading">
<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Distributed algorithm</span></span>
</h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">
<p>A <b>distributed algorithm</b> is an <a href="Algorithm" title="Algorithm">algorithm</a> designed to run on <a href="Computer_hardware" title="Computer hardware">computer hardware</a> constructed from interconnected <a href="Central_processing_unit" title="Central processing unit">processors</a>. Distributed algorithms are used in different application areas of <a href="Distributed_computing" title="Distributed computing">distributed computing</a>, such as <a href="Telecommunications" title="Telecommunications">telecommunications</a>, <a href="Scientific_computing" class="mw-redirect" title="Scientific computing">scientific computing</a>, distributed <a href="Data_processing" title="Data processing">information processing</a>, and real-time <a href="Process_control" class="mw-redirect" title="Process control">process control</a>. Standard problems solved by distributed algorithms include <a href="Leader_election" title="Leader election">leader election</a>, <a href="Consensus_(computer_science)" title="Consensus (computer science)">consensus</a>, distributed <a href="Search_algorithm" title="Search algorithm">search</a>, <a href="Spanning_tree_(mathematics)" class="mw-redirect" title="Spanning tree (mathematics)">spanning tree</a> generation, <a href="Mutual_exclusion" title="Mutual exclusion">mutual exclusion</a>, and <a href="Resource_allocation" title="Resource allocation">resource allocation</a>.<sup id="cite_ref-lynch1997_1-0" class="reference"><a href="#cite_note-lynch1997-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>
</p><p>Distributed algorithms are a sub-type of <a href="Parallel_algorithm" title="Parallel algorithm">parallel algorithm</a>, typically executed <a href="Concurrency_(computer_science)" title="Concurrency (computer science)">concurrently</a>, with separate parts of the algorithm being run simultaneously on independent processors, and having limited information about what the other parts of the algorithm are doing. One of the major challenges in developing and implementing distributed algorithms is successfully coordinating the behavior of the independent parts of the algorithm in the face of processor failures and unreliable communications links. The choice of an appropriate distributed algorithm to solve a given problem depends on both the characteristics of the problem, and characteristics of the system the algorithm will run on such as the type and probability of processor or link failures, the kind of <a href="Inter-process_communication" title="Inter-process communication">inter-process communication</a> that can be performed, and the level of timing synchronization between separate processes.<sup id="cite_ref-lynch1997_1-1" class="reference"><a href="#cite_note-lynch1997-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>
</p>
<meta property="mw:PageProp/toc">
<div class="mw-heading mw-heading2"><h2 id="Standard_problems">Standard problems</h2></div>
<dl><dt><a href="Atomic_commit" title="Atomic commit">Atomic commit</a></dt>
<dd>An atomic commit is an operation where a set of distinct changes is applied as a single operation. If the atomic commit succeeds, it means that all the changes have been applied. If there is a failure before the atomic commit can be completed, the "commit" is aborted and no changes will be applied.</dd>
<dd>Algorithms for solving the atomic commit problem include the <a href="Two-phase_commit_protocol" title="Two-phase commit protocol">two-phase commit protocol</a> and the <a href="Three-phase_commit_protocol" title="Three-phase commit protocol">three-phase commit protocol</a>.</dd>
<dt><a href="Consensus_(computer_science)" title="Consensus (computer science)">Consensus</a></dt>
<dd>Consensus algorithms try to solve the problem of a number of processes agreeing on a common decision.</dd>
<dd>More precisely, a Consensus protocol must satisfy the four formal properties below.
<ul><li><b>Termination</b>: every correct process decides some value.</li>
<li><b>Validity</b>: if all processes propose the same value <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>v</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle v}</annotation>
</semantics>
</math></span><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"></span>, then every correct process decides <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>v</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle v}</annotation>
</semantics>
</math></span><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"></span>.</li>
<li><b>Integrity</b>: every correct process decides at most one value, and if it decides some value <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>v</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle v}</annotation>
</semantics>
</math></span><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"></span>, then <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>v</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle v}</annotation>
</semantics>
</math></span><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"></span> must have been proposed by some process.</li>
<li><b>Agreement</b>: if a correct process decides <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>v</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle v}</annotation>
</semantics>
</math></span><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"></span>, then every correct process decides <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>v</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle v}</annotation>
</semantics>
</math></span><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"></span>.</li></ul></dd>
<dd>Common algorithms for solving consensus are the <a href="Paxos_algorithm" class="mw-redirect" title="Paxos algorithm">Paxos algorithm</a> and the <a href="Raft_(computer_science)" class="mw-redirect" title="Raft (computer science)">Raft algorithm</a>.</dd>
<dt>Distributed search</dt>
<dt><a href="Leader_election" title="Leader election">Leader election</a></dt>
<dd>Leader election is the process of designating a single process as the organizer of some task distributed among several computers (nodes). Before the task is begun, all network nodes are unaware of which node will serve as the "leader," or coordinator, of the task. After a leader election algorithm has been run, however, each node throughout the network recognizes a particular, unique node as the task leader.</dd>
<dt><a href="Mutual_exclusion" title="Mutual exclusion">Mutual exclusion</a></dt>
<dt><a href="Non-blocking_data_structures" class="mw-redirect" title="Non-blocking data structures">Non-blocking data structures</a></dt>
<dt><a href="Terminating_Reliable_Broadcast" title="Terminating Reliable Broadcast">Reliable Broadcast</a></dt>
<dd>Reliable broadcast is a communication primitive in distributed systems. A reliable broadcast is defined by the following properties:
<ul><li><b>Validity</b> - if a correct process sends a message, then some correct process will eventually deliver that message.</li>
<li><b>Agreement</b> - if a correct process delivers a message, then all correct processes eventually deliver that message.</li>
<li><b>Integrity</b> - every correct process delivers the same message at most once and only if that message has been sent by a process.</li></ul></dd>
<dd>A reliable broadcast can have sequential, causal or total ordering.</dd>
<dt><a href="Replication_(computer_science)" class="mw-redirect" title="Replication (computer science)">Replication</a></dt>
<dt><a href="Resource_allocation" title="Resource allocation">Resource allocation</a></dt>
<dt><a href="Spanning_tree" title="Spanning tree">Spanning tree</a> generation</dt>
<dt>Symmetry breaking, e.g. <a href="Vertex_coloring" class="mw-redirect" title="Vertex coloring">vertex coloring</a></dt></dl>
<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>
<style data-mw-deduplicate="TemplateStyles:r1239543626">
/* start https://en.wikipedia.org/ */
.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}
/* end https://en.wikipedia.org/ */
</style><div class="reflist">
<div class="mw-references-wrap"><ol class="references">
<li id="cite_note-lynch1997-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-lynch1997_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-lynch1997_1-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">
/* start https://en.wikipedia.org/ */
.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}
/* end https://en.wikipedia.org/ */
</style><cite id="CITEREFLynch1996" class="citation book cs1">Lynch, Nancy (1996). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/distributedalgor0000lync"><i>Distributed Algorithms</i></a></span>. San Francisco, CA: <a href="Morgan_Kaufmann_Publishers" title="Morgan Kaufmann Publishers">Morgan Kaufmann Publishers</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-55860-348-6</bdi>.</cite></span>
</li>
</ol></div></div>
<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>
<ul><li><cite id="CITEREFChristian_CachinRachid_GuerraouiLuís_Rodrigues2011" class="citation cs2">Christian Cachin; Rachid Guerraoui; Luís Rodrigues (2011), <i>Introduction to Reliable and Secure Distributed Programming</i> (2. ed.), Springer, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2011itra.book.....C">2011itra.book.....C</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-15259-7</bdi></cite></li>
<li>C. Rodríguez, M. Villagra and B. Barán, <a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FBIMNICS.2007.4610083">Asynchronous team algorithms for Boolean Satisfiability</a> , Bionetics2007, pp. 66–69, 2007.</li></ul>
<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>
<ul><li><span class="noviewer" typeof="mw:File"></span> Media related to <a href="https://commons.wikimedia.org/wiki/Category:Distributed_algorithms" class="extiw external" title="commons:Category:Distributed algorithms">Distributed algorithms</a> at Wikimedia Commons</li>
<li><a rel="nofollow" class="external text" href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-852j-distributed-algorithms-fall-2009/">MIT Open Courseware - Distributed Algorithms</a></li></ul></div><!--htdig_noindex--><div><div class="zim-footer">
This article is issued from <a class="external text" title="Last edited on 2025-06-23" href="https://en.wikipedia.org/wiki/?title=Distributed_algorithm&oldid=1297037923">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
</body></html>